Ітераційні методи розв`язання системи лінійних алгебраїчних рівнянь

Кафедра: Автоматика та інформаційні технології
"Ітераційних методів розв'язування СЛАР"
Єкатеринбург 2006

РІШЕННЯ СИСТЕМИ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ метод простої ітерації

Однією з найпоширеніших і важливих завдань обчислювальної математики є рішення системи лінійних алгебраїчних рівнянь (СЛАР):
a ₁₁ x ₁ + a ₁₂ x ₂ + ... + a _1n x _n = b ₁
a ₂₁ x ₁ + a ₂₂ x ₂ + ... + a ₂₁ x _n = b ₂
... ... ... ... ... ... ... ... ... ... ... ... ... .... .
a _n1 x ₁ + a _n1 x ₂ + ... + a _nn x _n = b _n,
або у векторно-матричному вигляді:
Ax = B, (1)
де
А11 А12 ...... А1N
А21 А22 - ... .. а2n
А = ................
аn1 аn2 .... ann
b1
b2
B =
bn
x1
x2
x =
xn
Ітераційні методи розв'язування СЛАР використовуються для вирішення СЛАР великої розмірності з розрідженими матрицями, а також для уточнення рішення СЛАР, отриманого за допомогою прямого методу. Формулювання і застосування ітераційних методів вимагає певних знань і певного досвіду. Вибір ефективного ітераційного методу розв'язання конкретного завдання істотно залежить від її характерних властивостей і від архітектури обчислювальної машини, на якій буде вирішуватися завдання. Тому ніяких загальних правил вибору найкращого ітераційного методу рішення не існує. Метод простої ітерації наведено тут як ілюстрація дії механізму обчислення рішення на основі ітераційної процедури.
Суть методу полягає в наступному. Від системи рівнянь виду Ах = в (2) переходять до системи рівнянь
x = D х + С (3)
Наприклад, від системи рівнянь
а ₁₁ х ₁ + а ₁₂ х ₂ + а ₁₃ х ₃ = в ₁
а ₂₁ х ₁ + а ₂₂ х ₂ + а ₂₃ х ₃ = в _{2 (4)}
а ₃₁ х ₁ + а ₃₂ х ₂ + а ₃₃ х ₃ = в ₃
можна перейти до виду (3), висловивши з першого рівняння х _1, з другого - х _2, з третього - х _3:
х ₁ = - а ₁₂ / а ₁₁ х ₂ - а ₁₃ / а ₁₁ х ₃ + у ₁ / а ₁₁
х ₂ = - а ₂₁ / а ₂₂ х ₁ - а ₂₃ / ​​а ₂₂ х ₃ + у ₂ / а _{22 (5)}
х ₃ = - а ₃₁ / а ₃₃ х ₁ - а ₃₂ / а ₃₃ х ₂ + у ₃ / а ₃₃
Приведення вихідної системи рівнянь на увазі (3) можна здійснити різними способами. Наприклад, в СЛАР (4) з першого рівняння можна виразити х _2, з другого - х _1, з третього - х ₃ і, переставивши рівняння для збереження порядку слідування змінних у векторі рішення х, знову прийти до виду (3). Природно, що матриця D і вектор з будуть вже іншими. Можливі й інші способи перетворення вихідних рівнянь.
Після перетворення (2) до виду (3) призначається нульове наближення розв'язку х ^(0):
х ₁ ⁽⁰⁾
х ⁽⁰⁾ = х ₂ ⁽⁰⁾
х ₃ ^(0).
Якщо приблизно відомі значення х _i вектора рішення х, то вони вибираються як нульове наближення, якщо ні, то як вектора х ⁽⁰⁾ вибирається будь-який вектор, наприклад х ⁽⁰⁾ = С.
Перший крок ітераційного процесу полягає в обчисленні наближення г ^(1):
г ⁽¹⁾ = Dx ⁽⁰⁾ + С.
Наприклад, призначивши х ⁽⁰⁾ і підставивши його в систему рівнянь (3), отримаємо:
х ^{_{1 (1)}} = - а ₁₂ / а ₁₁ х ^{(0) -} а ₁₃ / а ₁₁ х ₃ ⁽⁰⁾ + в ₁ / а ₁₁
х ₂ ⁽¹⁾ = - а ₂₁ / а ₂₂ х ₁ ^{(0) -} а ₂₃ / ​​а ₂₂ х ₃ ⁽⁰⁾ + у ₂ / а ₂₂
х ₃ ⁽⁰⁾ = - а ₃₁ / а ₃₃ х ₁ ^{(0) -} а ₃₂ / а ₃₃ х ₂ ⁽⁰⁾ + у ₃ / а _33.
Далі обчислюємо:
г ⁽²⁾ = Dx ⁽¹⁾ + C
х ^(к) = D х ^(к-1) + С
і т.д.
Достатня умова збіжності методу ітерації полягає в наступному, якщо норма матриці D (позначається ║ D ║) менше 1, то система рівнянь (3) має єдине рішення х ^* й ітерації сходяться до цього рішення зі швидкістю геометричної прогресії Іншими словами, якщо
║ D ║ <1, (6)
то
ℓ im ║ х ^{(к) -} х ^* ║ = 0
^{до → ∞}
і виконується тотожність
х ^* = D х ^* + С.
Як норми матриці D використовуються норми ║ D ║ ₁ або
║ D ║ _{∞: n}
║ D ║ ₁ = max Σ | d _ij |,
^{j i = 1}
_n
║ D ║ _∞ = max Σ | d _ij |.
^{i j = 1}
Аналогічно вводяться норми вектора х:
_n
║ х ║ ₁ = Σ | х _i |
_{i = 1}
║ х ║ _∞ = max | x _i |.
ⁱ
З умови збіжності (6) ясно, що не всяке перетворення вихідної системи (2) до виду (3) дозволить отримати рішення рівняння на основі ітераційного процесу, а тільки таке, котре забезпечить виконання умови ║ D ║ <1. Важливо мати на увазі, що при виконанні цієї умови ітераційний процес сходиться для будь-якого початкового наближення х ⁽⁰⁾ і вибір х ⁽⁰⁾ = С диктується просто міркуваннями зручності призначення х ^(0).
Якщо задана допустима похибка обчислень Δ, то для оцінки похибки до - го наближення широко використовується наступне нерівність:
║ х ^{(к) -} х * ║ ≤ ║ D ║ / (1 ​​- ║ D ║) • ║ х ^(к) - х ^(к-1) ║ <Δ (7)
З цієї нерівності слід критерій закінчення ітераційного процесу
║ х ^{(к) -} х ^(к-1) ║ <(1 - ║ D ║) • Δ / ║ D ║ (8)
Кожного разу при обчисленні чергового наближення х ^(k) перевіряється виконання нерівності (8).
Виконання нерівності (8) означає виконання нерівності
║ х ^(к) - х ^* ║ <Δ
і, отже, припинення ітераційного процесу.

ЗАВДАННЯ НА ВИКОНАННЯ РОБОТИ

Перевірити виконання умови збіжності ітераційного процесу.
Знайти рішення СЛАР, задаючи різні значення вектора початкового наближення до вирішення x ⁽⁰⁾ і фіксуючи кількість ітерацій, необхідних для досягнення рішення із заданою точністю.
Побудувати графіки x _i ^(k), _{i = 1, n} рішення в залежності від номера ітерації k.
Варіанти завдань до теми "Рішення СЛАР методом ітерацій"
Варіанти завдань до теми "Рішення СЛАР методом ітерацій"
Варіанти завдань до теми "Рішення СЛАР методом ітерацій"
Варіанти завдань до теми "Рішення СЛАР методом ітерацій"

Список літератури

1. Вержбицький В.М. Основи чисельних методів: Підручник для вузів. - М.: Вищ. шк., 2002. - 840с.
2. Волков О.О. Чисельні методи: Навчальний посібник. - 3-е изд., Испр. - СПб: Лань, 2004. - 248с.
3. Кетков Ю.Л. MATLAB 6: програмування чисельних методів. - СПб.: БВХ-Петербург, 2004. - 672с.
4. Турчак Л.І. Основи чисельних методів: Навчальний посібник. - М.: Наука. Гол. ред. фіз. - Мат. лит., 1987. - 320с.
5. Ітераційних методів розв'язування СЛАР: Методичні вказівки до лабораторної роботи з дисципліни "Обчислювальна математика" / сост. І.А. Селіванова. Єкатеринбург: ГОУ ВПО УГТУ-УПІ, 2006. - 12 с.
6. Вказівки призначені для студентів всіх форм навчання спеціальності 230101 - "Обчислювальні машини, комплекси, системи та мережі" та бакалаврів з напряму 230100 - "Інформатика та обчислювальна техніка".